package william.array;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author ZhangShenao
 * @date 2024/3/4
 * @description <a href="https://leetcode.cn/problems/intersection-of-two-arrays-ii/description/">...</a>
 */
public class Leetcode350_两个数组的交集2 {
    /**
     * 借助Map实现
     * 首先将nums1中的原始及其出现的频率保存在map中
     * 然后遍历nums2,如果当前元素出现在map中,则保存当前元素,并将map中对应元素的频率—1
     * <p>
     * 时间复杂度O(N) 两个数组各遍历一遍
     * 空间复杂度O(N) 需要额外申请一个map和一个list保存中间结果
     */
    public int[] intersect(int[] nums1, int[] nums2) {
        //边界条件校验
        if (nums1 == null || nums1.length < 1 || nums2 == null || nums2.length < 1) {
            return new int[0];
        }

        //遍历nums1,将所有元素及其出现的频率保存在Map中
        Map<Integer, Integer> frequency = new HashMap<>(nums1.length);
        for (int n : nums1) {
            if (frequency.containsKey(n)) {
                frequency.put(n, frequency.get(n) + 1);
            } else {
                frequency.put(n, 1);
            }
        }

        List<Integer> intersect = new ArrayList<>(nums2.length);
        //遍历nums2,如果当前元素出现在map中,则保存当前元素,并将map中对应元素的频率—1
        for (int n : nums2) {
            if (!frequency.containsKey(n)) {
                continue;
            }
            int fre = frequency.get(n);
            if (fre > 0) {
                intersect.add(n);
                frequency.put(n, fre - 1);
            }
        }

        //将结果转换成数组返回
        int[] result = new int[intersect.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = intersect.get(i);
        }
        return result;
    }
}
